/******************************************
Cola_implementacion_lista.java
Universidad del Valle de Guatemala
Algoritmos y Estructura de Datos
Autor:
    Martín Guzmán
Fecha: 7 de noviembre de 2009
Descripción: Implementación de un grafo
*******************************************/

import java.lang.reflect.Array;
import java.lang.AssertionError;
import java.util.LinkedList;

public class Grafo<G> extends Grafo_Abstracto<G> {

    public Grafo(){
        super();
    }

    public void Agregar_nodo(G nombre) {
        if(super.getAdjacency_map().contains(nombre)){
            System.out.println(">> El nodo que está tratando de agregar ya se encuentra");
        }
        else{
            super.adjacency_map.add(nombre);
            super.edges_list.add(new LinkedList<Nodo<Integer>>());
        }

    }

    public void Agregar_enlace(G nodo_fuente, G nodo_destino, Integer peso) {

        //System.out.println("mapa adyacencia: "+super.getAdjacency_map().size()+" Enlaces:"+super.getEdges_list().size());//DEBUGUEAR
        int temp = super.getAdjacency_map().indexOf(nodo_fuente);
        Nodo<Integer> temporal = new Nodo<Integer>(nodo_destino.toString(),peso);
        //quita lo que había
        if (super.adjacency_map.contains(nodo_fuente)==false){
            System.out.println("Lo siento, primer nodo no existe");
        }
        else if(super.adjacency_map.contains(nodo_destino)){
            super.edges_list.get(temp).add(temporal);
        }
        
        else{
            System.out.println("Lo siento, segundo nodo no existe");
        }


    }


    public String toString(){
        String temp="";
        for(int i=0;i<super.adjacency_map.size();i++){
            temp+=i+"- "+super.adjacency_map.get(i)+" ->\t";
            for(int j=0;j<super.edges_list.get(i).size();j++){
                temp+=super.edges_list.get(i).get(j)+" ";
            }
            temp+="\n";
        }
        return temp;
    }






    public String Algoritmo_Dijkstra(G nodo_inicial){
        return Calcular_ruta_mas_corta(nodo_inicial);
    }

    public String Calcular_ruta_mas_corta(G nodo_inicial) {

        valores_minimos = null;
        nodos_pasados = null;

        valores_minimos = new int[this.adjacency_map.size()];
        viene_de = new Object[this.adjacency_map.size()];

        nodos_pasados = new boolean[this.adjacency_map.size()];

        for(int i=0;i<valores_minimos.length;i++){
            valores_minimos[i]=100000000;
            nodos_pasados[i]=false;
            viene_de[i]=null;
        }

        this.nodo_inicial=nodo_inicial;
        int posicion_del_nodo_inicial = this.adjacency_map.indexOf(this.nodo_inicial);

        valores_minimos[posicion_del_nodo_inicial]=0;//desde si hasta si mismo es cero
        viene_de[posicion_del_nodo_inicial] = this.adjacency_map.get(posicion_del_nodo_inicial);

        //System.out.println(this.toString());

        //calcular el minimo de cada nodo inicial a todos los siguientes
        for(int i=0;i<valores_minimos.length;i++){

            calcular_minimo_a_todos(posicion_del_nodo_inicial);
            posicion_del_nodo_inicial = proxima_iteracion();
        }

        String resultado="";
        resultado+="------------------------------------------------------------\n";
        resultado+="|\tNodo ==>  ruta más corta para llegar a él ==> Viene de\n";

        for(int a=0;a<this.valores_minimos.length;a++){
            if(valores_minimos[a]==100000000){
                resultado+="|\t"+this.adjacency_map.get(a)+" ==> No es posible llegar.\n";
            }
            else
                resultado+="|\t"+this.adjacency_map.get(a)+" ==> "+this.valores_minimos[a]+" ==> "+this.viene_de[a]+"\n";
        }
        resultado+="------------------------------------------------------------\n";
        return resultado;
    }

    private void calcular_minimo_a_todos(int posicion_del_nodo_inicial) {
        LinkedList<Nodo<Integer>> lista = this.edges_list.get(posicion_del_nodo_inicial);
        //System.out.println("Lista de "+this.adjacency_map.get(posicion_del_nodo_inicial)+": "+lista);

        this.nodos_pasados[posicion_del_nodo_inicial]=true;

        for(int j=0;j<lista.size();j++){
            int posicion = this.adjacency_map.indexOf(lista.get(j).getNombre());
            //int valor = lista.get(j).getElemento();
            int valor = lista.get(j).getElemento()+valores_minimos[posicion_del_nodo_inicial];

            //comparar si es menor al que tiene
            if (valor < this.valores_minimos[posicion]){
                valores_minimos[posicion]=valor;
                viene_de[posicion] = this.adjacency_map.get(posicion_del_nodo_inicial);
            }
            //sino lo ignora
        }
        /*
        //prueba****************
        System.out.println("Lista de valores minimos");
        for(int j=0;j<valores_minimos.length;j++){
            System.out.println(valores_minimos[j]);
        }
        //**********************
        */
    }

    private G nodo_inicial;
    private int[] valores_minimos;
    private boolean[] nodos_pasados;
    private Object [] viene_de;

    private int proxima_iteracion() {
        //encontrar el nodo por el que no se haya pasado y que tenga el minimo peso

        int minimo = 100000000;
        int posicion_minimo=0;

        for(int k=0;k<valores_minimos.length;k++){
            if(this.nodos_pasados[k]==false){
                if(this.valores_minimos[k]<minimo){
                    minimo=valores_minimos[k];
                    posicion_minimo=k;
                }
            }
        }

        return posicion_minimo;
    }



}